Cos'è spanning tree?

Un albero di copertura (spanning tree) in un grafo è un sottoinsieme di archi che connette tutti i vertici del grafo senza formare cicli. Il termine "spanning tree" si riferisce al fatto che l'albero "spazia" su tutti i vertici del grafo come un albero di copertura.

In un grafo non orientato e connesso, esiste sempre almeno un albero di copertura chiamato albero di copertura minimo (minimum spanning tree). Il problema di trovare un minimum spanning tree è di grande importanza pratica in molte applicazioni, come reti di comunicazione, reti stradali, distribuzione di energia e altro ancora.

L'algoritmo più noto per trovare un minimum spanning tree è l'algoritmo di Kruskal e l'algoritmo di Prim. Entrambi gli algoritmi utilizzano la tecnica dell'algoritmo greedy per trovare un minimum spanning tree in modo efficiente.

Un'altra applicazione importante degli spanning tree è nell'algoritmo di broadcast in una rete di computer, dove l'albero di copertura è utilizzato per instradare in modo efficiente i messaggi a tutti i nodi della rete.